1. Field of the Disclosure
This disclosure relates generally to shared data structures, and more particularly to systems and methods for utilizing futures to improve performance of multicore systems that utilize long-lived shared data structures.
2. Description of the Related Art
A future is a data object that represents a promise to deliver the result of an asynchronous computation when it is ready. Futures are considered an attractive way to manage parallel computations in that they are simple to use, and they lend themselves well to efficient scheduling mechanisms such as work-stealing. A future's value is calculated sometime between when that future is created and when it is evaluated. Futures were originally proposed as benign annotations for side-effect-free computations that reference shared objects. Since these futures were short-lived tasks without side effects, it was impossible to observe when these computations actually happened. As originally proposed, futures were untyped and implicit. In other words, any object reference could be a future, and a run-time check was needed on each dereference. In more recently proposed versions, futures are usually typed, and future creation and evaluation are explicit.
An alternative proposal for implementing futures in languages in which side effects are common specifies that futures should satisfy a strong futures linearizability constraint and does not consider type-specific optimizations. An existing system that employs call streams and promises operates to batch a collection of service calls (e.g., in a distributed system in which service calls are directed to remote machines) to reduce communication costs. In this existing system, executions of the batched calls are pipelined and their answers are obtained later. Another existing system employs dual data structures, which are objects whose methods are split into a request method that registers the invocation and returns a ticket, and a follow-up method that takes the ticket as an argument, and returns either the request's response or a “not ready” indicator (for example, if trying to dequeue from an empty queue). These dual data structures provide a new way to implement linearizable partial methods, and rely primarily on a polling mechanism to determine when an operation has been performed.